package com.qiong.algorithm;

import java.util.Arrays;

/**
 * 找零钱：https://leetcode-cn.com/problems/coin-change/
 * 解法：https://labuladong.github.io/algo/3/23/68/#%E4%BA%8C%E5%87%91%E9%9B%B6%E9%92%B1%E9%97%AE%E9%A2%98
 * @Author: Liqc
 * @Date: 2022/5/5 13:21
 */
public class CoinChange {

    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
//        int i = coinChange.violentSolution(new int[]{1,2,5}, 11);
//        System.out.println(coinChange.violentSolution(new int[]{1}, 2));
//        System.out.println(coinChange.betterSolution(new int[]{1}, 2));
//        System.out.println(coinChange.betterSolution(new int[]{1,2,5}, 11));
        System.out.println(coinChange.bestSolution(new int[]{1}, 2));
        System.out.println(coinChange.bestSolution(new int[]{1,2,5}, 11));
    }

    /**
     * 暴力解法
     *
     * 凑出来 amount 需要多少个零钱
     *
     * @param coins
     * @param amount
     * @return
     */
    int violentSolution(int[] coins, int amount) {
        // 结束条件 base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int count = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subCount = violentSolution(coins, amount - coin);
            // -1 表示无法凑出
            if (subCount == -1) continue;
            // 加上本次零钱数，所以要加 1
            count = Math.min(count, subCount + 1);
        }
        // 防止第一个就无解的情况，如 [2], 3
        return count == Integer.MAX_VALUE? -1 : count;
    }

    int[] remember;

    /**
     * 暴力解法-带备忘录的
     *
     * 凑出来 amount 需要多少个零钱
     *
     * @param coins
     * @param amount
     * @return
     */
    int betterSolution(int[] coins, int amount) {
        // 使用一个数组记录已经计算过的值
        remember = new int[amount + 1];

        // 填充一个不可能存在的值
        Arrays.fill(remember, -678);

        return dp(coins, amount);
    }

    int dp(int[] coins, int amount) {
        // 结束条件 base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        // 如果有记录的值，直接返回
        if (remember[amount] != -678) {
            return remember[amount];
        }

        int count = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 计算子问题的结果
            int subCount = dp(coins, amount - coin);
            // -1 表示无法凑出
            if (subCount == -1) continue;
            // 加上本次零钱数，所以要加 1
            count = Math.min(count, subCount + 1);
        }
        // 结果放入数组中
        remember[amount] = count == Integer.MAX_VALUE? -1 : count;
        return remember[amount];
    }

    int[] dp;
    /**
     * dp 数组的迭代解法 - 自下向上
     *
     * 凑出来 amount 需要多少个零钱
     *
     * # 初始化 base case
     * dp[0][0][...] = base
     * # 进行状态转移
     * for 状态1 in 状态1的所有取值：
     *     for 状态2 in 状态2的所有取值：
     *         for ...
     *             dp[状态1][状态2][...] = 求最值(选择1，选择2...)
     *
     * @param coins
     * @param amount
     * @return
     */
    int bestSolution(int[] coins, int amount) {
        // 使用一个数组记录已经计算过的值
        dp = new int[amount + 1];

        // 填充一个不可能存在的值，不用 Integer.MAX_VALUE 是为了防止溢出
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;

        // 遍历所有状态值
        for (int i = 0; i < dp.length; i++) {
            // 内循环，循环求所有选择的最小值
            for (int coin : coins) {
                // 无解则跳过（i 表示要凑的钱）
                if (i - coin < 0) {
                    continue;
                }
                // 比较是否最小，最小则替换
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        // 如果 dp[amount] 等于 amount + 1 则说明是默认值，则无解
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }


}
